package hero.mps.leet_code_2;

/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 *
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 *
 * 你可以按任意顺序返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 * 示例 2：
 *
 * 输入：nums = [3,2,4], target = 6
 * 输出：[1,2]
 * 示例 3：
 *
 * 输入：nums = [3,3], target = 6
 * 输出：[0,1]
 *
 */

public class TwoListNodeAdd {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        // 打印链表
        public void printLinkedList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " -> ");
                current = current.next;
            }
            System.out.println("null");
        }
    }
    /**
     * 将两个逆序链表相加并返回新的逆序链表
     *
     * @param L1 第一个逆序链表
     * @param L2 第二个逆序链表
     * @return 相加后得到的新逆序链表
     */
    public ListNode addReverse(ListNode L1, ListNode L2) {
        // 创建一个哑节点作为结果链表的头节点
        ListNode dummyHead = new ListNode(0);
        // q指向L1的头节点，p指向L2的头节点，curr指向哑节点的下一个节点
        ListNode q= L1, p=L2, curr = dummyHead;
        // 进位初始化为0
        int carry = 0;
        // 当q或p不为空时，继续循环
        while (q != null || p != null) {
            // 如果q不为空，取q节点的值；否则取0
            int x = (q != null) ? q.val : 0;
            // 如果p不为空，取p节点的值；否则取0
            int y = (p != null) ? p.val : 0;
            // 计算当前位的和
            int sum = x + y + carry;
            // 更新进位
            carry = sum / 10;
            // 创建新节点，值为和的个位数
            curr.next = new ListNode(sum % 10);
            // 如果p不为空，则移动到下一个节点
            if (p != null) p = p.next;
            // 如果q不为空，则移动到下一个节点
            if (q != null) q = q.next;
            // 移动curr到下一个节点
            curr = curr.next;
        }
        // 如果还有进位，则创建新节点保存进位
        if (carry > 0)
            curr.next = new ListNode(carry);

        // 返回哑节点的下一个节点作为结果链表的头节点
        return dummyHead.next;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carray = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 == null ? 0 : l1.val;
            int n2 = l2 == null ? 0 : l2.val;
            int sum = n1 + n2 + carray;
            if (head==null){
                head = tail = new ListNode(sum % 10);
            }else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carray = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carray > 0){
            tail.next = new ListNode(carray);
            tail = tail.next;
        }
        return head;
    }

    // 将数组转换为链表
    public ListNode arrayToList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        ListNode head = null;
        ListNode tail = null;
        for (int val : arr) {
            if (head == null) {
                head = tail = new ListNode(val);
            }else {
                tail.next = new ListNode(val);
                tail = tail.next;
            }
        }
        return head; // 返回链表的头节点
    }

    public static void main(String[] args) {
        int[] arr1 = {9,9,9,9,9,9,9};
        int[] arr2 = {9,9,9,9};


        TwoListNodeAdd twoAdd = new TwoListNodeAdd();
        ListNode l1 = twoAdd.arrayToList(arr1);
        ListNode l2 = twoAdd.arrayToList(arr2);
        ListNode listNode = twoAdd.addReverse(l1, l2);
//        ListNode.printLinkedList(listNode);
    }
}
